package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 覃国强
 * @date 2022-07-12 15:47
 */
public class 题库_0227_基本计算器II {

  public static void main(String[] args) {
    String s = "1*2-3/4+5*6-7*8+9/10";
    System.out.println(new Solution().calculate(s));
  }


  static
  class Solution {
    public int calculate(String s) {
      if (s == null || s.length() == 0) {
        return 0;
      }

      Deque<Integer> numStack = new ArrayDeque<>();
      Deque<Character> symbolStack = new ArrayDeque<>();
      StringBuilder num = new StringBuilder();
      for (int i = 0; i < s.length(); ++i) {
        if (Character.isDigit(s.charAt(i))) {
          num.append(s.charAt(i));
        }

        if ((i == s.length() - 1 || !Character.isDigit(s.charAt(i))) && num.length() > 0) {
          numStack.push(Integer.parseInt(num.toString()));
          num = new StringBuilder();
        }

        if (isSymbol(s.charAt(i))) {
          while (!symbolStack.isEmpty() && isHighPrioritySymbol(symbolStack.peek(), s.charAt(i))) {
            calculate(numStack, symbolStack);
          }
          symbolStack.push(s.charAt(i));
        }
      }

      while (!symbolStack.isEmpty()) {
        calculate(numStack, symbolStack);
      }

      return numStack.pop();
    }

    private void calculate(Deque<Integer> numStack, Deque<Character> symbolStack) {
      int right = numStack.pop();
      int left = numStack.pop();
      char symbol = symbolStack.pop();
      int answer;
      switch (symbol) {
        case '+':
          answer = left + right;
          break;
        case '-':
          answer = left - right;
          break;
        case '*':
          answer = left * right;
          break;
        default:
          answer = left / right;
      }
      numStack.push(answer);
    }

    private boolean isHighPrioritySymbol(char left, char right) {
      if ('+' == right || '-' == right) {
        return true;
      }
      return '*' == left || '/' == left;
    }

    private boolean isSymbol(char symbol) {
      return '*' == symbol || '/' == symbol || '+' == symbol || '-' == symbol;
    }

  }

}









